/**
 * 链表实现队列
 */
#include <iostream>
#include <stdexcept>

using namespace std;

template <typename T>
class Queue
{
    struct Node
    {
        T data;     // 数据
        Node *next; // 指针
        Node() : next(nullptr) {}
        Node(T t) : data(t), next(nullptr) {}
        Node(T t, Node *n) : data(t), next(n) {}
    };

private:
    Node *front; // 头
    Node *rear;  // 尾
    int size;

public:
    Queue() : front(nullptr), rear(nullptr), size(0) {}
    ~Queue();

    void enqueue(T element); // 入队
    T dequeue();             // 出队
    T getFront() const;      // 获取头
    int getSize() const;     // 获取大小
    void print();            // 打印
};

template <typename T>
Queue<T>::~Queue()
{
    while (front)
    {
        Node *pTemp = front;
        front = front->next;
        delete pTemp;
    }
    delete rear;
}

template <typename T>
void Queue<T>::enqueue(T element)
{
    Node *newNode = new Node(element);
    if (rear == nullptr)
    {
        rear = newNode;
        front = rear;
    }
    else
    {
        rear->next = newNode;
        rear = newNode;
    }
    ++size;
}

template <typename T>
T Queue<T>::dequeue()
{
    if (front == nullptr)
    {
        throw std::underflow_error("Queue is empty");
    }
    T element = front->data;
    Node *pTemp = front;
    front = front->next;
    delete pTemp;
    --size;
    if (size == 0)
    {
        rear == nullptr;
    }
    return element;
}

template <typename T>
T Queue<T>::getFront() const
{
    if (front == nullptr)
    {
        throw std::underflow_error("Queue is empty");
    }
    return front->data;
}

template <typename T>
int Queue<T>::getSize() const
{
    return size;
}

template <typename T>
void Queue<T>::print()
{
    while (front)
    {
        cout << front->data << " ";
        dequeue();
    }
    cout << endl;
}

int main()
{
    Queue<int> q1;
    q1.enqueue(1);
    q1.enqueue(12);
    q1.enqueue(23);
    q1.enqueue(34);
    q1.enqueue(45);
    q1.enqueue(56);
    cout << "队列头：" << q1.getFront() << "队列大小：" << q1.getSize() << endl;
    q1.dequeue();
    cout << "队列头：" << q1.getFront() << "队列大小：" << q1.getSize() << endl;

    q1.print();
    cout << q1.getSize() << endl;
    return 0;
}